package 数据结构;

import common.ListNode;
import common.RandomListNode;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-11-27 15:00
 * 链表
 */
public class List01 {
    /**==============================================================================================================================================
     * JZ6 从尾到头打印链表
     * 输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
     * 1、栈：按顺序压入栈然后再输出
     * 2、反转链表，先反转，后按顺序加入到list中
    * */
    public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        Stack<Integer> stack=new Stack<>();
        while (listNode!=null){
            stack.push(listNode.val);
            listNode=listNode.next;
        }
        ArrayList<Integer> res=new ArrayList<>();
        while (!stack.isEmpty()){
            res.add(stack.pop());
        }
        return res;
    }

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res=new ArrayList<>();
        if (listNode==null) return res;
        ListNode pre=null,head=listNode;
        while (head.next!=null){
            ListNode next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        head.next=pre;
        while (head!=null){
            res.add(head.val);
            head=head.next;
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ24 反转链表
     * 给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。
     * 1、迭代
     * 2、递归
     * 3、栈
     * 4、双链表，用新链表来存储
     * */
    public ListNode ReverseList1(ListNode head) {
        if (head==null) return null;
        ListNode pre=null,cur=head;
        while (cur.next!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        cur.next=pre;
        return cur;
    }
    public ListNode ReverseList2(ListNode head) {
        //base case
        if (head==null) return null;
        if (head.next==null) return head;
        ListNode newHead=ReverseList2(head.next);
        //将head和反转后的链表的最后一个（即head.next，反转后head.next.next=null在最尾巴上）连接
        head.next.next=head;
        //让head成为最后
        head.next=null;
        return newHead;
    }
    public ListNode ReverseList(ListNode head) {
        if (head==null||head.next==null) return head;
        Stack<ListNode> stack=new Stack<>();
        while (head!=null){
            stack.push(head);
            head=head.next;
        }
        ListNode newHead=stack.pop();
        ListNode cur=newHead;
        while (!stack.isEmpty()){
            cur.next=stack.pop();
            cur=cur.next;
        }
        cur.next=null;
        return newHead;
    }

    /**==============================================================================================================================================
     * JZ25 合并两个排序的链表
     * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
     * 双指针
     * */
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1==null) return list2;
        if (list2==null) return list1;
        ListNode mhead=null;
        if (list1.val<list2.val){
            mhead=list1;
            list1=list1.next;
        }else {
            mhead=list2;
            list2=list2.next;
        }
        ListNode mList=mhead,p1=list1,p2=list2;
        while (p1!=null&&p2!=null){
            if (p1.val<p2.val){
                mList.next=p1;
                p1=p1.next;
            }else {
                mList.next=p2;
                p2=p2.next;
            }
            mList=mList.next;
        }
       mList.next=p1==null? p2:p1;
        return mhead;
    }

    /**==============================================================================================================================================
     * JZ52 两个链表的第一个公共结点
     * 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
     * 1、双指针:p1到达最后后，到pHead2.
     *       p2到达最后。接着遍历pHead1----直到两个指针相遇，就是两个链表的第一个公共节点
     * 2、set判断
     * */
    public ListNode FindFirstCommonNode1(ListNode pHead1, ListNode pHead2) {
        if (pHead1==null||pHead2==null) return null;
        ListNode p1=pHead1,p2=pHead2;
        while (p1!=p2){
            //当两个链表没有公共节点时，在两个指针同时遍历完了两个链表后都到达null
            if (p1==null){
                p1=pHead2;
            }else {
                p1=p1.next;
            }
            if (p2==null){
                p2=pHead1;
            }else {
                p2=p2.next;
            }
        }
        return p1;
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1==null||pHead2==null) return null;
        Set<ListNode> set=new HashSet<>();
        while (pHead1!=null){
            set.add(pHead1);
            pHead1=pHead1.next;
        }
        while (pHead2!=null){
            if (set.contains(pHead2))return pHead2;
            pHead2=pHead2.next;
        }
        return null;
    }

    /**==============================================================================================================================================
     * JZ23 链表中环的入口结点
     * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
     * 1、快慢指针：快指针每次走两步，当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
     * 2、用set判断
     * */
    public ListNode EntryNodeOfLoop1(ListNode pHead) {
        if (pHead==null||pHead.next==null) return null;
        ListNode fast=pHead,slow=pHead;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow)break;
        }
        //没有环
        if (fast==null||fast.next==null) return null;
        //将其中一个指针从头开始遍历
        slow=pHead;
        while (slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead==null||pHead.next==null) return null;
        Set<ListNode> set=new HashSet<>();
        while (pHead!=null){
            if (set.contains(pHead))return pHead;
            set.add(pHead);
            pHead=pHead.next;
        }
        return null;
    }

    /**==============================================================================================================================================
     * JZ22 链表中倒数最后k个结点
     * 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。如果该链表长度小于k，请返回一个长度为 0 的链表。
     * 快慢指针：快指针先走k步，然后慢指针从头开始，当快指针到最后时，慢指针的位置即为倒数第k个节点
     * */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (k==0||pHead==null)return null;
        ListNode slow=pHead,fast=pHead;
        while (k>0&&fast!=null){
            fast=fast.next;
            k--;
        }
        if (k>0) return null;
        while (fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }

    /**==============================================================================================================================================
     * JZ35 复杂链表的复制
     * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点
     * 1、递归+map
     * 2、迭代：在每个节点后面添加一个复制节点，再复制每个节点的random执行原本random的下一个，最后遍历将原链表和新链表进行拆分即可
     * */
    Map<RandomListNode,RandomListNode> cacheSet=new HashMap<>();
    public RandomListNode Clone1(RandomListNode pHead) {
        if (pHead==null) return null;
        if (cacheSet.containsKey(pHead)) return cacheSet.get(pHead);
        RandomListNode newNode=new RandomListNode(pHead.label);
        cacheSet.put(pHead,newNode);
        newNode.next=Clone(pHead.next);
        newNode.random=Clone(pHead.random);
        return newNode;
    }
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead==null)return null;
        RandomListNode node=pHead;
        //在每个节点后面接一个复制节点
        while (node!=null){
            RandomListNode newnode=new RandomListNode(node.label);
            newnode.next=node.next;
            node.next=newnode;
            node=node.next.next;
        }
        node=pHead;
        //将复制的节点的random复制
        while (node!=null){
            RandomListNode newnode=node.next;
            newnode.random=node.random==null?null:node.random.next;
            node=node.next.next;
        }
        //拆分
        RandomListNode resHead=pHead.next;
        node=pHead;
        while (node!=null){
            RandomListNode newnode=node.next;
            node.next=node.next.next;
            newnode.next=newnode.next==null?null:newnode.next.next;
            node=node.next;
        }
        return resHead;
    }
    /**==============================================================================================================================================
     * JZ76 删除链表中重复的结点
     * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
     * 双指针：i指针记录没有重复的最后一个节点，j指针遍历，判断j与j.next的值是否重复，有重复时需要找到最后一个重复元素，将i.next赋值为没有重复的
     * */
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead==null||pHead.next==null)return pHead;
        ListNode i=new ListNode(0);
        i.next=pHead;
        ListNode res=i;
        ListNode j=pHead;
        while (j!=null){
            if (j.next!=null&&j.val==j.next.val){
                //当前j为重复元素
                j=j.next;
                //找到与j重复的最长位置
                while (j.next!=null&&j.val==j.next.val){
                    j=j.next;
                }
                j=j.next;
                i.next=j;
            }else {
                //当前j不是重复元素
                i=j;
                j=j.next;
            }
        }
        return res.next;
    }

    /**==============================================================================================================================================
     * JZ18 删除链表的节点
     * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
     * 添加一个虚拟头节点，遍历判断下一个节点是不是val，是的话将当前节点的下一个节点赋值为下一个的next
     * */
    public ListNode deleteNode (ListNode head, int val) {
        if (head==null)return null;
        ListNode res=new ListNode(-1);
        res.next=head;
        ListNode p=res;
        while (p.next!=null){
            if (p.next.val==val){
                p.next=p.next.next;
                return res.next;
            }else {
                p=p.next;
            }
        }
        return res.next;
    }

}
